package learn.sort.heap;

import learn.CommUtil;

public class MyHeap {

    public int[] heap;
    public int length;
    public int size;

    public MyHeap(int length) {
        this.length = length;
        this.heap = new int[length];
        this.size = 0;
    }

    public void push(int val) {
        if (length == size) {
            throw new RuntimeException("heap 满了");
        }
        heap[size] = val;
        heapInsert(size++);
    }

    public int pollRoot() {
        int ans = heap[0];
        heap[0] = heap[--size];
        heap[size] = -1;//-1好观察
        //下沉
        heapify(0);
        return ans;
    }

    ;

    public void heapInsert(int index) {
        int father = -1;
        while (heap[index] > heap[father = (index - 1) / 2]) {
            CommUtil.swap(heap, index, father);
            index = father;
        }
    }

    public void heapify(int index) {
        int left = 2 * index + 1;
        while (left < size - 1) {
            int right = left + 1;
            //左右比
            int largest = heap[left] > heap[right] ? left : right;
            //上下比
            largest = heap[index] > heap[largest] ? index : largest;
            //
            if (largest == index) {
                break;
            }
            CommUtil.swap(heap, index, largest);
            index = largest;
            left = 2 * index + 1;
        }
    }

}
